Community structure

Many community identification methods use Modularity defined by Mark Newman. However, modularity and the “modularity picture” cannot incorporate highly Overlapping community structures.

It is considered that networks have hierarchical, or multi-scale community structures. There are some methods (See Link community or other papers¹).

Check out Paul Adams‘s slides and Adrien Friggeri‘s slides regarding real-world social community structure.

Topics

• Community detection, Graph partitioning
  • Spectral clustering
  • Block model
  • Cluster validation, Evaluation of community detection methods, Community comparison
  • Modularity
  • Bipartite community structure
  • Dynamic community structure
  • Overlapping community structure
    • Link community
  • Local community detection
  • Detectability of communities, Community detectability
  • Community resolution limit
• Information diffusion and communities
• Community formation

Review papers

• Community detection in graphs by Santo Fortunato
• Communities in Networks by Mason Porter, Jukka Pekka Onnela, Peter J
• The art of community detection by Natali Gulbahce, Sune Lehmann
• The many facets of community detection in complex networks
  • Different approaches to community detection
• The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness by Cristopher Moore

in Biology

• MCODE: http://www.biomedcentral.com/content/pdf/1471-2105-4-2.pdf
• http://bioinformatics.oxfordjournals.org/content/18/suppl_1/S233.abstract - jActive. using statistics.. check the papers that cite this.

in Physics

• Detecting fuzzy community structures in complex networks with a Potts model by Joerg Reichardt, Stefan Bornholdt

in Directed network

Many networks have directional edges. Examples are: emails, WWW, citation, Food web, softwares, … How do we find communities in the directed networks? What does a community mean in directed networks?

The concept of modularity has a deep connection to the Random walk, and thus it is easily generalizable to directed networks. Elizabeth Leicht and Mark Newman generalized the modularity²

• Youngdo Kim, Seung-Woo Son and Hawoong Jeong, Community Identification in Directed Networks, http://www.springerlink.com/content/t0q363x3580g30v0/
• E. A. Leicht, M. E. J. Newman, Community structure in directed networks, http://arxiv.org/abs/0709.4500
• Youngdo Kim, Seung-Woo Son, Hawoong Jeong, LinkRank: Finding communities in directed networks, http://arxiv.org/abs/arXiv:0902.3728
• Jacob G. Foster1, David V. Foster, Peter Grassberger, and Maya Paczuski, Edge direction and the structure of networks, http://www.pnas.org/content/107/24/10815.full
• Gergely Palla, Illés J Farkas, Péter Pollner, Imre Derényi and Tamás Vicsek, Directed network modules, http://iopscience.iop.org/1367-2630/9/6/186/
• Module identification in bipartite and directed networks, http://arxiv.org/abs/physics/0701151
• Maps of random walks on complex networks reveal community structure, http://arXiv.org/abs/0707.0609
• Laplacian Dynamics and Multiscale Modular Structure in Networks, http://arXiv.org/abs/0812.1770

• Flow graphs: interweaving dynamics and structure, http://lanl.arxiv.org/abs/1012.1211

• Naoki Masuda and Hisashi Ohtsuki, Evolutionary dynamics and fixation probabilities in directed networks, http://iopscience.iop.org/1367-2630/11/3/033012

• Community mining on dynamic weighted directed graphs, http://portal.acm.org/citation.cfm?id=1651274.1651278
• Impact of hierarchical modular structure on ranking of individual nodes in directed networks, http://iopscience.iop.org/1367-2630/11/11/113002
• Extending the definition of modularity to directed graphs with overlapping communities, http://iopscience.iop.org/1742-5468/2009/03/P03024
• Eigenvectors for clustering: Unipartite, bipartite, and directed graph cases, http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5559871
• Generation of arbitrary two-point correlated directed networks with given modularity, http://dx.doi.org/10.1016/j.physleta.2010.05.072
• Potential collaboration discovery using document clustering and community structure detection, http://portal.acm.org/citation.cfm?id=1651274.1651283

Community consistency

• Assessing the consistency of community structure in complex networks

Community structure and dynamics

• Laplacian Dynamics and Multiscale Modular Structure in Networks by Renaud Lambiotte et al.
• Flow graphs: Interweaving dynamics and structure by Renaud Lambiotte et al.
• Interplay between structure and dynamics in adaptive complex networks: Emergence and amplification of modularity by adaptive dynamics by Wu Jie Yuan and Changsong Zhou

Number of communities

• Estimating the number of communities in a network

References

• Community structure and scale-free collections of Erdős-Rényi graphs
• Followers Are Not Enough: Beyond Structural Communities in Online Social Networks
• Inferring large-scale patterns in complex networks - slides by Aaron Clauset
• A simple SVD algorithm for finding hidden partitions